1) Field of the Invention
The invention relates generally to communication over networks, and more particularly to error detection using cyclic redundancy checks.
2) Description of Background Art
Electronic information is often shared through computer networks. These networks can vary in size from small networks of just a few devices sharing information to large-scale global networks, such as the Internet. Regardless of the size, there must be a mechanism in every network to transport information. Information in the form of electrical signals are often transported through copper cable; information in the form of optical signals are transported through fiber optic cables; and other electromagnetic waves can be transported through the air.
FIG. 1 shows several devices connected together through an optical network 110. Optical networks have several advantages, including a large bandwidth, low susceptibility to interference, light-weight cables, and an ability to transmit information digitally rather than in analog. Devices attached to an optical network can include a switch 120, a server 140, and a network attached storage (NAS) 150 or any like device capable of transmitting and receiving data packets.
Switch 120 is an example of a device that filters and forwards packets of information between local area network (LAN) clients 130. Clients 130 can include a desktop computer, laptop, personal digital assistant (PDA), printer or other network attached device.
Server 140 controls network resources. For example a file server stores files, a print server manages one or more printers, a network server manages network traffic, and a database server processes database queries. Servers 140 can include UNIX servers, NT servers, Windows 2000 servers, LINUX servers, or other computer systems attached to the network. Network attached storage 150 is a special type of server 140 that is dedicated to file sharing and cannot perform other functions, such as authentication or file management.
Each device 120, 140, and 150 must have an interface circuit board 160 installed in order to communicate across optical network 110. Signals on optical network 110 travel at a rate faster than devices 120, 140, and 150 can understand. Also, optical signals are serialized (travel bit by bit) and devices 120, 140, and 150 use parallel data streams. Therefore, interface circuit board 160 translates serial optical signals into a slower, parallel data stream when receiving optical information, and conversely translates parallel data streams into faster, serial bit streams when transmitting information.
Interface circuit boards 160 known in the art use old Ethernet protocol standards. Specifically, old Ethernet protocols allowed throughputs of only 10 megabits per second over a network medium. However, a newer, faster, 10-Gigabit Ethernet standard has recently been defined. Interface circuit boards 160 designed to operate according to old Ethernet protocols cannot be readily adapted for use with the new standard because both translations from the transport medium to the devices on the network and collision detection mechanisms function differently.
In principal, both the old and new standards, however, rely on cyclic redundancy check (CRC) for determining when errors ore present in a data stream. A CRC performs a mathematical calculation on a data stream before and after data transmission. If the two results are identical, then it is assumed that no errors occurred during transmission.
Specifically, the mathematical calculation that is performed is division of the data stream by an agreed upon generator polynomial in modulo 2. Modular arithmetic, proposed by K. F. Gauss in 1801, assumes that two numbers are equal if, and only if, their difference is exactly divisible by N. In modulo 2 (or Mod-2) N is equal to 2. Although the details of modulo 2 division are beyond the scope of this document, it should be noted that one of the benefits of using modular arithmetic is that a relatively simple and well-known circuit can perform the necessary calculation.
FIG. 2 shows a circuit 200 that performs a bit-wise CRC calculation (i.e., a CRC calculation that is performed one bit at a time). The generator polynomial used in circuit 200 is X16+X14+X1+X0, which is represented as 10100000000000011 in base 2. In theory, any generator polynomial could be used, as long as both the transmitting and receiving end use the same polynomial. However, the above polynomial, called the CRC-16 Reverse polynomial, has been determined to be especially effective, and is used throughout the industry.
Input 205 to circuit 200 is the data stream, taken serially. In the first cycle the first bit of data, D0, is combined with the information in a delay flip flop fifteen 210, C15, using a first: XOR circuit 215, to produce a result. The result of first XOR circuit 215, D0 XOR C15, is then input directly in delay flip flop zero 220. Delay flip flop zero 220 inputs its original information, C0, to a delay flip flop one 225. Information that was contained in delay flip flop one 225, C1, is combined with the result from first XOR circuit 215, D0 XOR C15, with a second XOR circuit 230 and input in a delay flip flop two 235 to produce C1 XOR D0 XOR C15. Information that was in delay flip flop two 235, C2, is input to a delay flip flop three 240, which inputs its information, C3, into delay flip flop four 245. The process continues until each delay flip flop has updated information. The updated values after the first input cycle are shown in Table 1.
TABLE 1REGISTERVALUED_FF0D0 XOR C15D_FF1C0D_FF2C1 XOR D0 XOR C15D_FF3C2D_FF4C3D_FF5C4D_FF6C5D_FF7C6D_FF8C7D_FF9C8D_FF10C9D_FF11C10D_FF12C11D_FF13C12D_FF14C13D_FF15C14 XOR D0 XOR C15
In the next cycle (i.e., next data bit), the process is repeated, except with the second bit of data, D1. At the end of the second cycle the information in each delay flip flop can be expressed as a function of the initial information in the delay flip flops, C0–C15, and the two bits of data, D0 and D1. For example, information in delay flip flop zero 220 can be expressed as D1 XOR C14 XOR D0 XOR C15, information in delay flip flop one 225 can be expressed as D0 XOR C15. Table 2 shows the values in each register at the end of the second input cycle.
TABLE 2REGISTERVALUED_FF0D1 XOR C14 XOR D0 XOR C15D_FF1D0 XOR C15D_FF2C0 XOR D1 XOR C14 XOR D0 XOR C15D_FF3C1 XOR D0 XOR C15D_FF4C2D_FF5C3D_FF6C4D_FF7C5D_FF8C6D_FF9C7D_FF10C8D_FF11C9D_FF12C10D_FF13C11D_FF14C12D_FF15C13 XOR D1 XOR C14 XOR D0 XOR C15
The CRC calculation ends when there is no more data to input into the circuit. The final values in the delay flip flops are collectively called the residue, which is equal to the remainder of the data stream divided by the generator polynomial 10100000000000011 in mod-2 arithmetic. It should be noted that the values of C0, C1, C2 . . . C15 are zero in this circuit 200. As will be seen, C0, C1, C2 . . . C15 are only relevant for bit-wise calculations.
FIG. 3 shows a circuit 300 that performs a CRC calculation using a larger generator polynomial. The generator polynomial used in circuit 300 is X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X1+X0, which is represented as 100000100110000010001110110110111 in base 2, and is commonly called the CRC-32 polynomial. Circuit 300 works in a similar fashion as circuit 200.
However, both circuits 200 and 300 are very slow, taking a full cycle for every bit of data in the data stream. The process was significantly improved upon when circuits were created that calculated values a byte at a time instead of a bit at a time, as described in “Byte-wise CRC Calculations,” IEEE Micro, June 1983, pp. 40–50 by Aram Perez.
Aram Perez describes a process by which a bit-wise CRC circuit, such as circuit 200 or circuit 300 is first modeled. Next, the general values of each flip flop after eight bits (one byte) is calculated. Finally, a circuit that implements the calculations is created using, for example, automatic circuit design techniques. Table 3 shows the values in each register at the end of the eighth cycle using the CRC-16 Reverse polynomial from circuit 200 shown in FIG. 2. Although the values of C0, C1, C2 . . . C15 are initially zero, in later cycles they represent the residue in each register from the previous cycle.
TABLE 3REGISTERVALUE (XOR TAKEN OF MULTIPLE VALUES)D_FF0D0, D1, D2, D3, D4, D5, D6, D7, C8, C9, C10, C11, C12,C13, C14, C15D_FF1D0, D1, D2, D3, D4, D5, D6, C9, C10, C11, C12, C13,C14, C15D_FF2D6, D7, C8, C9D_FF3D5, D6, C9, C10D_FF4D4, D5, C10, C11D_FF5D3, D4, C11, C12D_FF6D2, D3, C12, C13D_FF7D1, D2, C13, C14D_FF8D0, D1, C0, C14, C15D_FF9D0, C1, C15D_FF10C2D_FF11C3D_FF12C4D_FF13C5D_FF14C6D_FF15D0, D1, D2, D3, D4, D5, D6, D7, C7, C8, C9, C10, C11,C12, C13, C14, C15
To one skilled in the art, creating a circuit that performs the above operations is trivial. Such a circuit would perform calculations eight times faster than circuit 200 or 300.
However, performing the CRC calculation is only one piece of the total CRC process. The rest of the process depends upon whether interface circuit board 160 is transmitting or receiving data. FIG. 4A shows the basic method used during the transmit process and FIG. 4B shows the basic method used during the receive process.
Step 410, where the actual CRC calculation is performed by either a bit-wise or a byte-wise CRC circuit, is the first step in the transmit process. Next, in step 420, a determination is made as to whether the data has been shifted.
Like any remainder, the CRC result represents how far away numerically the dividend is from being evenly divisible by the divisor. In regular division, the remainder must be subtracted from the dividend in order to be evenly divisible. For example, 17 divided by 4 gives a remainder of 1, which must be subtracted from 17 in order to make 16 and be evenly divisible by 4. (There are, of course, other relationships between the dividend, remainder and divisor, which are not important for this discussion.) However, in modular division, the remainder can be added to the dividend in order to make the number evenly divisible by the divisor. CRC transmitting circuits use this relationship by adding the remainder to the dividend so that the CRC receiving circuit will calculate a zero remainder if no error is present.
In order to prevent the CRC receiving circuit from then having to subtract the remainder from the dividend to retrieve the original data stream, the data is shifted prior to adding the remainder. Since the remainder will always be less than the generator polynomial the data only needs to be shifted by the same order of magnitude as the generator polynomial. If the CRC-32 polynomial were being used, 32 zeros would be appended to the data. Appending 32 zeros is equivalent to multiplying the data by 232. Therefore, the result from the CRC calculation is equal to the remainder from a mod 2 division, where the dividend is equal to the data multiplied by 232 and the divisor is equal to the CRC-32 polynomial.
Referring back to FIG. 4, if data has not been shifted step 420 directs the process to step 430, where the data is shifted the same order of magnitude as the generator polynomial and then directed back to step 410 for more CRC calculations.
Once data has been shifted, the process proceeds to step 440 where the CRC result is added to the shifted data. As previously mentioned, since the maximum possible remainder will always be less than or equal to the generator polynomial, the CRC result will at most replace the added zeros and never modify the actual data.
FIG. 4B shows the basic method used during the receive process. The process begins with step 410, the same step that is used in the transmit process. The same bit-wise or byte-wise CRC circuit that was used in the transmit process can also be used in the receive process. In step 450 the new CRC result is examined. If the result does not equal zero, then the system reports an error in step 470. 1f the remainder is zero, it is assumed that no error is present, and the process proceeds to step 460. In step 460 the data is truncated the same amount as it was shifted in step 430 from the transmit process. Therefore, step 460 returns the data back to its original state.
Although the byte-wise CRC calculation worked very well with the old Ethernet standard, the new 10-Gigabit Ethernet standard requires CRC calculations to be completed in a much shorter time.